// 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

// 说明：

// 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

// 示例 1:

// 输入: [2,2,3,2]
// 输出: 3
// 示例 2:

// 输入: [0,1,0,1,0,1,99]
// 输出: 99

#include <vector>

using namespace std;

// 建立一个32位的数字，来统计每一位上1出现的个数，如果某一位为1的话，那么如果该整数出现了三次，对3去余为0。把每个数的对应位都加起来对3取余，最终剩下来的那个数就是单独的数字。
class Solution1 {
public:
    int singleNumber(vector<int>& nums) {
        int res{0};
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (auto &num : nums)
                sum += (num >> i) & 1; // 和1与是因为只取一位
            res |= (sum % 3) << i;
        }
        return res;
    }
};

#include "stdc++.h"

/* 哈希表
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hashMap{};
        for (int& num : nums) {
            ++hashMap[num];
        }
        for (auto& p : hashMap) {
            if (p.second == 1) {
                return p.first;
            }
        }
        return 0;
    }
};

/* 依次确定每一个二进制位
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res{0};
        for (int i{0}; i < 32; ++i) {
            int total{0}; // 统计第 i 位 1 的个数
            for (int num : nums) {
                total += ((num >> i) & 1);
            }
            if (1 == total % 3) {
                res |= (1 << i);
            }
        }
        return res;
    }
};

/* 数字电路设计
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int num: nums) {
            // a,b 同时变化，所以需要临时变量暂存之前的值
            int newA = (~a & b & num) | (a & ~b & ~num);
            int newB = ~a & (b ^ num);
            a = newA;
            b = newB;
        }
        return b;
    }
};

/* 数字电路设计 - 优化
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int num: nums) {
            b = ~a & (b ^ num);
            a = ~b & (a ^ num);
        }
        return b;
    }
};
